package edu.cityu.cs.hk.datastructures;
import java.util.Iterator;
/**
  * A speedy implementation of the CompleteBinaryTree interface using
  * a vector.  Within the vector, there is a null element at rank 0,
  * the root of the tree at rank 1, and the rest of the tree is
  * contained as follows.  If node <code>n</code> has rank <i>i</i>,
  * then the left child of <code>n</code> will have rank 2*<i>i</i>,
  * and the right child of <code>n</code> will have rank 2*<i>i</i> +
  * 1.  Traversing the contents of the vector in order of increasing
  * rank yields a level-order traversal
  *
  * @author Michael Goodrich, Eric Zamore
  * @see BinaryTree
  * @see CompleteBinaryTree
  */

//begin#fragment VectorHeap
public class VectorCompleteBinaryTree implements CompleteBinaryTree  {
  protected Vector T;  // vector of elements stored in the tree
  /** Nested class for a vector-based complete binary tree node. */
  protected static class VectorNode implements Position {
    Object element; // element stored at this position
    int index;      // index of this position in the vector
    public VectorNode(Object elt, int i) { 
      element = elt;
      index = i; 
    }
    public Object element() { return element; }
    public int index() { return index; }
    public Object setElement(Object elt) {
      Object temp = element;
      element = elt;
      return temp;
    }
  }
  /** default constructor */
  public VectorCompleteBinaryTree() { 
    T = new ArrayVector();
    T.insertAtRank(0,null); // the location at rank 0 is deliberately empty
  }
  /** Returns the number of (internal and external) nodes. */
  public int size() { return T.size()-1; } 
  /** Returns whether the tree is empty. */ 
  public boolean isEmpty() { return (size()==0); } 
//end#fragment VectorHeap
//begin#fragment VectorHeap2
  /** Returns whether v is an internal node. */
  public boolean isInternal(Position v) throws InvalidPositionException {
    return hasLeft(v);  // if v has a right child it will have a left child
  }
  /** Returns whether v is an external node. */
  public boolean isExternal(Position v) throws InvalidPositionException {
    return !isInternal(v);
  }
  /** Returns whether v is the root node. */
  public boolean isRoot(Position v) throws InvalidPositionException { 
    VectorNode vv = checkPosition(v);
    return vv.index() == 1;
  }
  /** Returns whether v has a left child. */
  public boolean hasLeft(Position v) throws InvalidPositionException { 
    VectorNode vv = checkPosition(v);
    return 2*vv.index() <= size();
  }
  /** Returns whether v has a right child. */
  public boolean hasRight(Position v) throws InvalidPositionException { 
    VectorNode vv = checkPosition(v);
    return 2*vv.index() + 1 <= size();
  }
  /** Returns the root of the tree. */
  public Position root() throws EmptyTreeException {
    if (isEmpty()) throw new EmptyTreeException("Tree is empty");
    return (Position)T.elemAtRank(1);
  } 
  /** Returns the left child of v. */
  public Position left(Position v) 
    throws InvalidPositionException, BoundaryViolationException { 
    if (!hasLeft(v)) throw new BoundaryViolationException("No left child");
    return (Position)T.elemAtRank(2*((VectorNode) v).index());
  }
  /** Returns the right child of v. */ 
  public Position right(Position v) 
    throws InvalidPositionException { 
    if (!hasRight(v)) throw new BoundaryViolationException("No right child");
    return (Position)T.elemAtRank(2*((VectorNode) v).index() + 1);
  }
//end#fragment VectorHeap2
//begin#fragment VectorHeap3
  /** Returns the parent of v. */
  public Position parent(Position v) 
    throws InvalidPositionException, BoundaryViolationException { 
    if (isRoot(v)) throw new BoundaryViolationException("No parent");
    return (Position)T.elemAtRank(((VectorNode) v).index() / 2);
  }
//end#fragment VectorHeap3
  /** Returns an iterator of the children of v. */ 
  public Iterator children(Position v) throws InvalidPositionException { 
    List children = new NodeList();
    if (hasLeft(v))
      children.insertLast(left(v));
    if (hasRight(v))
      children.insertLast(right(v));
    return children.elements();
  }
  /** Returns an iterator of all nodes in the tree. */
  public Iterator positions() {
    List positions = new NodeList();
    if(!isEmpty())
      inorderPositions(root(), positions, 0);  // assign positions in inorder
    return positions.elements();
  }
//begin#fragment VectorHeap3
  /** Replaces the element at v. */
  public Object replace(Position v, Object o) throws InvalidPositionException {
    VectorNode vv = checkPosition(v);
    return vv.setElement(o);
  }
  /** Add an element just after the last node (in a level numbering). */
  public Position add(Object e) {
    int rankToInsert = size()+1;
    Position p = new VectorNode(e,rankToInsert);
    T.insertAtRank(rankToInsert,p);
    return p;
  }
  /** Removes and returns the element at the last node. */
  public Object remove() throws EmptyTreeException {
    if(isEmpty()) throw new EmptyTreeException("Tree is empty");
    return ((Position)T.removeAtRank(size())).element(); 
  }
  /** Determine whether v is a valid node. */
  protected VectorNode checkPosition(Position v) 
    throws InvalidPositionException 
  {
    if (v == null || !(v instanceof VectorNode))
      throw new InvalidPositionException("Position is invalid");
    return (VectorNode)v;
  }
//end#fragment VectorHeap3
  /** Fills a list according to an inorder traversal. */ 
  protected int inorderPositions(Position v, List pos, int i) 
    throws InvalidPositionException {
    if (hasLeft(v))
      i = inorderPositions(left(v), pos, i);  // recurse on left
    i++;
    pos.insertLast(v);  //  v has rank i in the inorder traversal
    if (hasRight(v))
      i = inorderPositions(right(v), pos, i); // recurse on right
    return i;
  }
  // Additional Methods
  /** Returns the sibling of v. */ 
  public Position sibling(Position v) 
    throws InvalidPositionException, BoundaryViolationException {
    try {
      Position p = parent(v);
      Position lc = left(p);
      if (v == lc)
	return right(p);
      else
	return lc;
    }
    catch(BoundaryViolationException e) {
      throw new BoundaryViolationException("Node has no sibling");
    }
  }
  /** Swaps the elements at two nodes. */
  public void swapElements(Position v, Position w)
    throws InvalidPositionException {
    VectorNode vv = checkPosition(v);
    VectorNode ww = checkPosition(w);
    Object temp = vv.element();
    vv.setElement(ww.element());
    ww.setElement(temp);
  }
//begin#fragment VectorHeap3
  /** Returns an iterator of the elements stored at all nodes in the tree. */
  public Iterator elements() { 
    List list = new NodeList();
    for(int i = 0; i < size(); i++)
      list.insertLast(((Position)T.elemAtRank(i+1)).element());
    return list.elements();
  } 
//end#fragment VectorHeap3
  /** Returns a String representing this complete binary tree. */
  public String toString() { return T.toString(); }
//begin#fragment VectorHeap3
} // methods children and positions are omitted here (same as LinkedBinaryTree)
//end#fragment VectorHeap3
